# Code by Phong Si
# builds a tree to find all unique permutations of a given array without duplicates
module TreePermute
  def tree_permute
    set = self.sort
    arr = Array.new
    arr << []
    set.each do |element| 
      if arr.last.last.eql?(element)
        arr.last << element
      else
        arr << [element]
      end
    end
    arr.delete_at(0)
    empty_sets = Array.new
    arr.size.times {empty_sets << []}
    buildPerms(arr, empty_sets, Array.new, Array.new)
  end
  private
    def buildPerms(arr, empty_sets, permutations, permutation)
      if (arr.eql?(empty_sets))
        permutations << permutation.dup
      else
        arr.each do |subset|
          if !subset.empty?
            permutation << subset.pop
            buildPerms(arr, empty_sets, permutations, permutation)
            subset << permutation.pop
          end
        end
      end
      return permutations
    end
end
